package dp;

import java.util.*;

public class _19_139_单词拆分 {
    public static boolean wordBreak(String s, List<String> wordDict) {
    	boolean dp[] = new boolean[s.length()+1];
    	Map<String,String> map = new HashMap<>(); // 用set做会更好
    	for (String word : wordDict) {
			map.put(word, word);
		}
    	dp[0] = true;
    	for(int i = 1; i <= s.length(); i++) { 
    		for(int j = 0; j < i; j++) { 
    			// dp[j]成立说明是true，说明在之前的搜索中发现从0-j能匹配到字典中的字符串
    			// map.get(s.substring(j,i)) != null 说明从j到i的字符串，符合字典中的某个单词 
    			if(dp[j] && map.get(s.substring(j,i)) != null) {
    				// 0到j有匹配的字典，并且j到i能匹配到字典
    				// 说明从0-i的字符串都能匹配到字典，说明dp[i]是true
    				dp[i] = true;
    			}
    		}
    	}

    	return dp[s.length()];
    }
    public static void main(String[] args) {
    	String s = "catsandog";
    	List<String> wordDict = new ArrayList<>();
    	wordDict.add("cats");
    	wordDict.add("dog");
    	wordDict.add("sand");
    	System.out.println(wordBreak(s, wordDict));
	}
}
